package com.algorithm.liyc.greedy;

/**
 * 0135.分发糖果
 *
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 *
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 * ● 每个孩子至少分配到 1 个糖果。
 * ● 相邻的孩子中，评分高的孩子必须获得更多的糖果。
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 *
 * 先确定右边评分大于左边的情况（也就是从前向后遍历）
 * 此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
 * 局部最优可以推出全局最优。
 * 再确定左孩子大于右孩子的情况一定要从后向前遍历！
 *
 * @author Liyc
 * @date 2024/1/29 15:54
 **/

public class Solution9 {
    /**
     * 分两个阶段
     * 1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
     * 2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，
     * 此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyNum = new int[len];
        candyNum[0] = 1;
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i-1]) {
                candyNum[i] = candyNum[i-1] + 1;
            }
        }
        for (int i = len-2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                candyNum[i] = Math.max(candyNum[i], candyNum[i+1]+1);
            }
        }
        int result = 0;
        for (int i = 0; i < candyNum.length; i++) {
            result += candyNum[i];
        }
        return result;
    }
}
